The Padlock Puzzle
I heard this puzzle many years ago, and do not remember the origins of it. The version below is from Peter Winkler’s paper Seven Puzzles You Think You Must Not Have Heard Correctly.
Puzzle. Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria’s hands?
I don’t know whether this puzzle appeared before the Diffie-Hellman key exchange was invented, but I am sure that one of them inspired the other. The official solution is that Jan sends Maria a box with the ring in it and one of his padlocks on it. Upon receipt Maria affixes her own padlock to the box and mails it back with both padlocks on it. When Jan gets it, he removes his padlock and sends the box back, locked only with Maria’s padlock. As Maria has her own key, she can now open it.
My students suggested many other solutions. I wonder if some of them can be translated to cryptography.
- Jan can send the ring in a padlock box that is made of cardboard. Maria can just cut the cardboard with a knife.
- Jan can use the magic of the Internet to send Maria schematics of the key so she can either 3d print it or get a professional to forge it. If they are afraid of the schematics getting stolen Jan can send the schematics after the package has been delivered.
- Jan can use a digital padlock and send the code using the Internet.
- Jan can send it in a secret puzzle box that can be opened without a key.
- Maria can smash the padlock with a hammer.
Now that we’ve looked at the Padlock Puzzle, let’s talk about cryptography. I have an imaginary student named Charlie who doesn’t know the Diffie-Hellman key exchange. Charlie decided that he can adapt the padlock puzzle to help Alice send a secret message to Bob. Here’s what Charlie suggests:
Suppose the message is M. Alice converts it to binary. Then she creates a random binary key A and XORs it with M. She sends the result, M XOR A, to Bob. Then Bob creates his own random key B and XORs it with what he receives and sends the result, M XOR A XOR B, back to Alice. Alice XORs the result with her key to get M XOR A XOR B XOR A = M XOR B and sends it to Bob. Bob XORs it with his key to decipher the message.
Each sent message is equivalent to a random string. Intercepting it is not useful to an evil eavesdropper. The scheme is perfect. Or is it?
Share:
YaronD:
Would be terrible against an eavesdropper that can intercept all three messages. XORing all three together is cleartext M…
Charlie misunderstands XOR, or that digital data can be recorded and kept for use in the future.
Should be fine against an eavesdropper that would only intercept one (or two) of the messages, though.
26 December 2019, 2:03 pmAbout Jan and Maria and their padlock(s) – The nth Root:
[…] Puzzle. Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria’s hands? I don’t know whether this puzzle appeared before the Diffie-Hellman key exchange was invented, but I am sure that one of them inspired the other. The official solution is… (Tanya Khovanova’s Math Blog) […]
28 December 2019, 7:04 pmSHREYAS:
If it is known to the interceptor that XOR is the function being used as the encrypting function, the exercise is pretty moot as the interceptor can easily back calculate the message.
8 March 2020, 3:39 pm